package com.ctrip.study.algorithm.pratice;

import org.junit.Test;

import junit.framework.TestCase;

public class LinkIntersect extends TestCase{
	
	@Test
	public void test(){
		Node node1 = new Node(1);
		Node node2 = new Node(2);
		Node node3 = new Node(3);
		Node node4 = new Node(4);
		Node node5 = new Node(5);
		Node node6 = new Node(6);
		Node node7 = new Node(7);
		Node node8 = new Node(8);
		Node node9 = new Node(9);
		Node node10 = new Node(10);
		Link link1 = new Link();
		Link link2 = new Link();
		link1.insert(node1);
		link1.insert(node2);
		link1.insert(node3);
		link1.insert(node4);
		node4.next = node9;
		node4.next.next = node10;
		
		link2.insert(node5);
		link2.insert(node6);
		link2.insert(node7);
		link2.insert(node8);
		node8.next = node9;
		node8.next.next = node10;
		
		boolean isIntersect = judgeIntersect(link1, link2);
		assertTrue(isIntersect);
		
	}
	
	
	/**
	 * 如果两个链表相交，
	 * 那个两个链表从相交点到链表结束都是相同的节点，
	 * 我们可以先遍历一个链表，直到尾部，
	 * 再遍历另外一个链表，
	 * 如果也可以走到同样的结尾点，则两个链表相交。
	 */
	private boolean judgeIntersect(Link link1, Link link2) {
		Node lastNode1 = link1.head;
		while(lastNode1.next != null){
			lastNode1 = lastNode1.next;
		}
		Node lastNode2 = link2.head;
		while(lastNode2.next != null){
			lastNode2 = lastNode2.next;
		}
		return lastNode1 == lastNode2;
	}






	private class Link{
		public Node head;
		public void insert(Node node){
			if(head == null){
				head = node;
			}else{
				Node currentNode = head;
				while(currentNode.next != null){
					currentNode = currentNode.next;
				}
				currentNode.next = node;
			}
		}
	}
	
	
	private class Node{
		public int data;
		public Node next;
		public Node(int data){
			this.data = data;
		}
		
		@Override
		public String toString() {
			return "Node [data=" + data +"]";
		}
	}

}
